package algorithm.leetcode.simple;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020/8/28
 */
public class Question22 {

    public static void main(String[] args) {

        Question22 question = new Question22();
        List<String> strings = question.generateParenthesis(3);
        for (String s : strings) {
            System.out.println(s);
        }
    }


    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>(10);
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }

    private void backtrack(List<String> result, StringBuilder cur, int openNum, int closeNum, int n) {
        // 这轮结束
        if (cur.length() == n * 2) {
            result.add(cur.toString());
            return;
        }

        if (openNum < n) {
            cur.append("(");
            backtrack(result, cur, openNum + 1, closeNum, n);
            cur.deleteCharAt(cur.length() - 1);
        }

        if (closeNum < openNum) {
            cur.append(")");
            backtrack(result, cur, openNum, closeNum + 1, n);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}
